﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace QueuesAndStacks.UpdateMatrix
{
    class MainProjecet
    {
        static void Main(string[] args)
        {
            int[][] nums = new int[][]
            {   new int[]{0 },
                new int[]{0 },
                  new int[]{0},
                new int[]{0},
            };
            int[][] s = UpdateMatrix(nums);
            for (int i = 0; i < s.Length; i++)
            {
                for (int j = 0; j < s[i].Length; j++)
                {
                    Console.WriteLine(s[i][j]);
                }
            }


            Console.ReadKey();
        }

        /// <summary>
        /// DP
        /// </summary>
        /// <param name="mat"></param>
        /// <returns></returns>
        public static int[][] UpdateMatrix(int[][] mat)
        {
            int m = mat.Length;
            int n = mat[0].Length;
            int[][] dp = new int[m][];
            for (int i = 0; i < m; i++) dp[i] = new int[n];

            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    dp[i][j] = mat[i][j] == 0 ? 0 : 10000;
                }
            }

            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (i - 1 >= 0) dp[i][j] = Math.Min(dp[i - 1][j] + 1, dp[i][j]);
                    if (j - 1 >= 0) dp[i][j] = Math.Min(dp[i][j - 1] + 1, dp[i][j]);
                }
            }
            for (int i = m-1; i >=0; i--)
            {
                for (int j = n-1; j >=0; j--)
                {
                    if (i + 1 < m) dp[i][j] = Math.Min(dp[i + 1][j] + 1, dp[i][j]);
                    if (j + 1 > n) dp[i][j] = Math.Min(dp[i][j + 1] + 1, dp[i][j]);
                }
            }
            return dp;
        }

        /// <summary>
        /// 图 多源广度搜索
        /// </summary>
        /// <param name="mat"></param>
        /// <returns></returns>
        public static int[][] UpdateMatrix2(int[][] mat)
        {
            int m = mat.Length;
            int n = mat[0].Length;
            Queue<int[]> que = new Queue<int[]>();
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (mat[i][j] == 0)
                    {
                        que.Enqueue(new int[] { i, j });
                    }
                    else
                    {
                        mat[i][j] = -1;
                    }
                }
            }
            int[] dx = new int[] { -1, 1, 0, 0 };
            int[] dy = new int[] { 0, 0, 1, -1 };
            while (que.Any())
            {
                int size = que.Count;

                for (int i = 0; i < size; i++)
                {
                    int[] unit = que.Dequeue();
                    for (int j = 0; j < 4; j++)
                    {
                        int newX = unit[0] + dx[j];
                        int newY = unit[1] + dy[j];

                        if (newX >= 0 && newX < m && newY >= 0 && newY < n && mat[newX][newY] == -1)
                        {
                            mat[newX][newY] = mat[unit[0]][unit[1]] + 1;
                            que.Enqueue(new int[] { newX, newY });
                        }
                    }
                }
            }
            return mat;
        }
        /// <summary>
        /// (Tree的单源BFS)BFS可以 超时了
        /// </summary>
        /// <param name="mat"></param>
        /// <returns></returns>
        public static int[][] UpdateMatrix1(int[][] mat)
        {
            //BFS
            Dictionary<int, int> dic = new Dictionary<int, int>();
            for (int i = 0; i < mat.Length; i++)
            {
                for (int j = 0; j < mat[i].Length; j++)
                {

                    if (mat[i][j] != 0)
                    {
                        //int count = 0;
                        //int returnValue = Matrix(mat, i, j, dic);
                        //mat[i][j] = returnValue;
                    }

                }
            }
            return mat;
        }

        public static int Matrix(int[][] mat, int i, int j)
        {
            //BFS 超时问题
            Queue<int> que = new Queue<int>();
            HashSet<int> hash = new HashSet<int>();

            que.Enqueue(i * 10000 + j);
            hash.Add(i * 10000 + j);
            int nums = -1;
            while (que.Any())
            {
                int size = que.Count;
                bool havaZero = false;
                for (int k = 0; k < size; k++)
                {
                    int code = que.Dequeue();

                    int x = code / 10000;
                    int y = code % 10000;

                    if (mat[x][y] == 0) { havaZero = true; que.Clear(); break; }
                    if ((x - 1) >= 0 && hash.Add((x - 1) * 10000 + y)) que.Enqueue((x - 1) * 10000 + y);
                    if ((x + 1) < mat.Length && hash.Add((x + 1) * 10000 + y)) que.Enqueue((x + 1) * 10000 + y);
                    if ((y - 1) >= 0 && hash.Add(x * 10000 + y - 1)) que.Enqueue(x * 10000 + y - 1);
                    if ((y + 1) < mat[x].Length && hash.Add(x * 10000 + y + 1)) que.Enqueue(x * 10000 + y + 1);
                }
                nums++;
                if (havaZero) return nums;
            }
            return nums;
        }
    }
}
